# Copyright (c) 2009 Peter Corbett
#
# Permission is hereby granted, free of charge, to any person
# obtaining a copy of this software and associated documentation
# files (the "Software"), to deal in the Software without
# restriction, including without limitation the rights to use,
# copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the
# Software is furnished to do so, subject to the following
# conditions:
#
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
# OTHER DEALINGS IN THE SOFTWARE.

import bisect
import random

class Selector:
    def __init__(self, d):
        self.d = d
        self.outcomes = []
        self.cfs = []
        self.cf = 0.0

        for k in d:
            if d[k] <= 0: continue
            self.cf += d[k]
            self.outcomes.append(k)
            self.cfs.append(self.cf)

    def select(self):
        r = random.uniform(0, self.cf)
        i = bisect.bisect(self.cfs, r)
        return self.outcomes[i]

if __name__=="__main__":
    d = {"a": 1, "b": 0.0001, "c": 10.1, "d": 0.1}
    sel = Selector(d)
    l = [sel.select() for i in range(100000)]
    #print l
    print l.count("a")
    print l.count("b")
    print l.count("c")
    print l.count("d")
